home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / findutil.1 / findutil / findutils-4.1 / locate / locate.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-26  |  10.4 KB  |  403 lines
  1. /* locate -- search databases for filenames that match patterns
  2.    Copyright (C) 1994 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Usage: locate [options] pattern...
  19.  
  20.    Scan a pathname list for the full pathname of a file, given only
  21.    a piece of the name (possibly containing shell globbing metacharacters).
  22.    The list has been processed with front-compression, which reduces
  23.    the list size by a factor of 4-5.
  24.    Recognizes two database formats, old and new.  The old format is
  25.    bigram coded, which reduces space by a further 20-25% and uses the
  26.    following encoding of the database bytes:
  27.  
  28.    0-28        likeliest differential counts + offset (14) to make nonnegative
  29.    30        escape code for out-of-range count to follow in next halfword
  30.    128-255     bigram codes (the 128 most common, as determined by `updatedb')
  31.    32-127      single character (printable) ASCII remainder
  32.  
  33.    Uses a novel two-tiered string search technique:
  34.  
  35.    First, match a metacharacter-free subpattern and a partial pathname
  36.    BACKWARDS to avoid full expansion of the pathname list.
  37.    The time savings is 40-50% over forward matching, which cannot efficiently
  38.    handle overlapped search patterns and compressed path remainders.
  39.  
  40.    Then, match the actual shell glob-style regular expression (if in this form)
  41.    against the candidate pathnames using the slower shell filename
  42.    matching routines.
  43.  
  44.    Described more fully in Usenix ;login:, Vol 8, No 1,
  45.    February/March, 1983, p. 8.
  46.  
  47.    Written by James A. Woods <jwoods@adobe.com>.
  48.    Modified by David MacKenzie <djm@gnu.ai.mit.edu>.  */
  49.  
  50. #include <config.h>
  51. #include <stdio.h>
  52. #include <sys/types.h>
  53. #include <sys/stat.h>
  54. #include <time.h>
  55. #include <fnmatch.h>
  56. #include <getopt.h>
  57.  
  58. #define NDEBUG
  59. #include <assert.h>
  60.  
  61. #if defined(HAVE_STRING_H) || defined(STDC_HEADERS)
  62. #include <string.h>
  63. #else
  64. #include <strings.h>
  65. #define strchr index
  66. #endif
  67.  
  68. #ifdef STDC_HEADERS
  69. #include <stdlib.h>
  70. #else
  71. char *getenv ();
  72. #endif
  73.  
  74. #ifdef STDC_HEADERS
  75. #include <errno.h>
  76. #include <stdlib.h>
  77. #else
  78. extern int errno;
  79. #endif
  80.  
  81. #include "locatedb.h"
  82.  
  83. typedef enum {false, true} boolean;
  84.  
  85. /* Warn if a database is older than this.  8 days allows for a weekly
  86.    update that takes up to a day to perform.  */
  87. #define WARN_SECONDS (60 * 60 * 24 * 8)
  88.  
  89. /* Printable version of WARN_SECONDS.  */
  90. #define WARN_MESSAGE "8 days"
  91.  
  92. char *next_element ();
  93. char *xmalloc ();
  94. char *xrealloc ();
  95. void error ();
  96.  
  97. /* Read in a 16-bit int, high byte first (network byte order).  */
  98.  
  99. static int
  100. get_short (fp)
  101.      FILE *fp;
  102. {
  103.   register short x;
  104.  
  105.   x = fgetc (fp);
  106.   return (x << 8) | (fgetc (fp) & 0xff);
  107. }
  108.  
  109. /* Return a pointer to the last character in a static copy of the last
  110.    glob-free subpattern in NAME,
  111.    with '\0' prepended for a fast backwards pre-match.  */
  112.  
  113. static char *
  114. last_literal_end (name)
  115.      char *name;
  116. {
  117.   static char *globfree = NULL;    /* A copy of the subpattern in NAME.  */
  118.   static size_t gfalloc = 0;    /* Bytes allocated for `globfree'.  */
  119.   register char *subp;        /* Return value.  */
  120.   register char *p;        /* Search location in NAME.  */
  121.  
  122.   /* Find the end of the subpattern.
  123.      Skip trailing metacharacters and [] ranges. */
  124.   for (p = name + strlen (name) - 1; p >= name && strchr ("*?]", *p) != NULL;
  125.        p--)
  126.     {
  127.       if (*p == ']')
  128.     while (p >= name && *p != '[')
  129.       p--;
  130.     }
  131.   if (p < name)
  132.     p = name;
  133.  
  134.   if (p - name + 3 > gfalloc)
  135.     {
  136.       gfalloc = p - name + 3 + 64; /* Room to grow.  */
  137.       globfree = xrealloc (globfree, gfalloc);
  138.     }
  139.   subp = globfree;
  140.   *subp++ = '\0';
  141.  
  142.   /* If the pattern has only metacharacters, make every path match the
  143.      subpattern, so it gets checked the slow way.  */
  144.   if (p == name && strchr ("?*[]", *p) != NULL)
  145.     *subp++ = '/';
  146.   else
  147.     {
  148.       char *endmark;
  149.       /* Find the start of the metacharacter-free subpattern.  */
  150.       for (endmark = p; p >= name && strchr ("]*?", *p) == NULL; p--)
  151.     ;
  152.       /* Copy the subpattern into globfree.  */
  153.       for (++p; p <= endmark; )
  154.     *subp++ = *p++;
  155.     }
  156.   *subp-- = '\0';        /* Null terminate, though it's not needed.  */
  157.  
  158.   return subp;
  159. }
  160.  
  161. /* Print the entries in DBFILE that match shell globbing pattern PATHPART.
  162.    Return the number of entries printed.  */
  163.  
  164. static int
  165. locate (pathpart, dbfile)
  166.      char *pathpart, *dbfile;
  167. {
  168.   /* The pathname database.  */
  169.   FILE *fp;
  170.   /* An input byte.  */
  171.   int c;
  172.   /* Number of bytes read from an entry.  */
  173.   int nread;
  174.  
  175.   /* true if PATHPART contains globbing metacharacters.  */
  176.   boolean globflag;
  177.   /* The end of the last glob-free subpattern in PATHPART.  */
  178.   char *patend;
  179.  
  180.   /* The current input database entry.  */
  181.   char *path;
  182.   /* Amount allocated for it.  */
  183.   size_t pathsize;
  184.  
  185.   /* The length of the prefix shared with the previous database entry.  */
  186.   int count = 0;
  187.   /* Where in `path' to stop the backward search for the last character
  188.      in the subpattern.  Set according to `count'.  */
  189.   char *cutoff;
  190.  
  191.   /* true if we found a fast match (of patend) on the previous path.  */
  192.   boolean prev_fast_match = false;
  193.   /* The return value.  */
  194.   int printed = 0;
  195.  
  196.   /* true if reading a bigram-encoded database.  */
  197.   boolean old_format = false;
  198.   /* For the old database format,
  199.      the first and second characters of the most common bigrams.  */
  200.   char bigram1[128], bigram2[128];
  201.  
  202.   /* To check the age of the database.  */
  203.   struct stat st;
  204.   time_t now;
  205.  
  206.   if (stat (dbfile, &st) || (fp = fopen (dbfile, "r")) == NULL)
  207.     {
  208.       error (0, errno, "%s", dbfile);
  209.       return 0;
  210.     }
  211.   time(&now);
  212.   if (now - st.st_mtime > WARN_SECONDS)
  213.     {
  214.       error (0, 0, "warning: database `%s' is more than %s old",
  215.          dbfile, WARN_MESSAGE);
  216.     }
  217.  
  218.   pathsize = 1026;        /* Increased as necessary by getstr.  */
  219.   path = xmalloc (pathsize);
  220.  
  221.   nread = fread (path, 1, sizeof (LOCATEDB_MAGIC), fp);
  222.   if (nread != sizeof (LOCATEDB_MAGIC)
  223.       || memcmp (path, LOCATEDB_MAGIC, sizeof (LOCATEDB_MAGIC)))
  224.     {
  225.       int i;
  226.       /* Read the list of the most common bigrams in the database.  */
  227.       fseek (fp, 0, 0);
  228.       for (i = 0; i < 128; i++)
  229.     {
  230.       bigram1[i] = getc (fp);
  231.       bigram2[i] = getc (fp);
  232.     }
  233.       old_format = true;
  234.     }
  235.  
  236.   globflag = strchr (pathpart, '*') || strchr (pathpart, '?')
  237.     || strchr (pathpart, '[');
  238.  
  239.   patend = last_literal_end (pathpart);
  240.  
  241.   c = getc (fp);
  242.   while (c != EOF)
  243.     {
  244.       register char *s;        /* Scan the path we read in.  */
  245.  
  246.       if (old_format)
  247.     {
  248.       /* Get the offset in the path where this path info starts.  */
  249.       if (c == LOCATEDB_OLD_ESCAPE)
  250.         count += getw (fp) - LOCATEDB_OLD_OFFSET;
  251.       else
  252.         count += c - LOCATEDB_OLD_OFFSET;
  253.  
  254.       /* Overlay the old path with the remainder of the new.  */
  255.       for (s = path + count; (c = getc (fp)) > LOCATEDB_OLD_ESCAPE;)
  256.         if (c < 0200)
  257.           *s++ = c;        /* An ordinary character.  */
  258.         else
  259.           {
  260.         /* Bigram markers have the high bit set. */
  261.         c &= 0177;
  262.         *s++ = bigram1[c];
  263.         *s++ = bigram2[c];
  264.           }
  265.       *s-- = '\0';
  266.     }
  267.       else
  268.     {
  269.       if (c == LOCATEDB_ESCAPE)
  270.         count += get_short (fp);
  271.       else if (c > 127)
  272.         count += c - 256;
  273.       else
  274.         count += c;
  275.  
  276.       /* Overlay the old path with the remainder of the new.  */
  277.       nread = getstr (&path, &pathsize, fp, '\0', count);
  278.       if (nread < 0)
  279.         break;
  280.       c = getc (fp);
  281.       s = path + count + nread - 2; /* Move to the last char in path.  */
  282.       assert (s[0] != '\0');
  283.       assert (s[1] == '\0'); /* Our terminator.  */
  284.       assert (s[2] == '\0'); /* Added by getstr.  */
  285.     }
  286.  
  287.       /* If the previous path matched, scan the whole path for the last
  288.      char in the subpattern.  If not, the shared prefix doesn't match
  289.      the pattern, so don't scan it for the last char.  */
  290.       cutoff = prev_fast_match ? path : path + count;
  291.  
  292.       /* Search backward starting at the end of the path we just read in,
  293.      for the character at the end of the last glob-free subpattern
  294.      in PATHPART.  */
  295.       for (prev_fast_match = false; s >= cutoff; s--)
  296.     /* Fast first char check. */
  297.     if (*s == *patend)
  298.       {
  299.         char *s2;        /* Scan the path we read in. */
  300.         register char *p2;    /* Scan `patend'.  */
  301.  
  302.         for (s2 = s - 1, p2 = patend - 1; *p2 != '\0' && *s2 == *p2;
  303.                            s2--, p2--)
  304.           ;
  305.         if (*p2 == '\0')
  306.           {
  307.         /* Success on the fast match.  Compare the whole pattern
  308.            if it contains globbing characters.  */
  309.         prev_fast_match = true;
  310.         if (globflag == false || fnmatch (pathpart, path, 0) == 0)
  311.           {
  312.             puts (path);
  313.             ++printed;
  314.           }
  315.         break;
  316.           }
  317.       }
  318.     }
  319.  
  320.   if (ferror (fp))
  321.     {
  322.       error (0, errno, "%s", dbfile);
  323.       return 0;
  324.     }
  325.   if (fclose (fp) == EOF)
  326.     {
  327.       error (0, errno, "%s", dbfile);
  328.       return 0;
  329.     }
  330.  
  331.   return printed;
  332. }
  333.  
  334. extern char *version_string;
  335.  
  336. /* The name this program was run with. */
  337. char *program_name;
  338.  
  339. static void
  340. usage (stream, status)
  341.      FILE *stream;
  342.      int status;
  343. {
  344.   fprintf (stream, "\
  345. Usage: %s [-d path] [--database=path] [--version] [--help] pattern...\n",
  346.        program_name);
  347.   exit (status);
  348. }
  349.  
  350. static struct option const longopts[] =
  351. {
  352.   {"database", required_argument, NULL, 'd'},
  353.   {"help", no_argument, NULL, 'h'},
  354.   {"version", no_argument, NULL, 'v'},
  355.   {NULL, no_argument, NULL, 0}
  356. };
  357.  
  358. void
  359. main (argc, argv)
  360.      int argc;
  361.      char **argv;
  362. {
  363.   char *dbpath;
  364.   int found = 0, optc;
  365.  
  366.   program_name = argv[0];
  367.  
  368.   dbpath = getenv ("LOCATE_PATH");
  369.   if (dbpath == NULL)
  370.     dbpath = LOCATE_DB;
  371.  
  372.   while ((optc = getopt_long (argc, argv, "d:", longopts, (int *) 0)) != -1)
  373.     switch (optc)
  374.       {
  375.       case 'd':
  376.     dbpath = optarg;
  377.     break;
  378.  
  379.       case 'h':
  380.     usage (stdout, 0);
  381.  
  382.       case 'v':
  383.     printf ("GNU locate version %s\n", version_string);
  384.     exit (0);
  385.  
  386.       default:
  387.     usage (stderr, 1);
  388.       }
  389.  
  390.   if (optind == argc)
  391.     usage (stderr, 1);
  392.  
  393.   for (; optind < argc; optind++)
  394.     {
  395.       char *e;
  396.       next_element (dbpath);    /* Initialize.  */
  397.       while ((e = next_element ((char *) NULL)) != NULL)
  398.     found |= locate (argv[optind], e);
  399.     }
  400.  
  401.   exit (!found);
  402. }
  403.